\section{Up-and-put option}
In this problem we will consider two estimators for estimating the price the of an "up-and-put" option
\begin{align}
e^{-rT}\paren{K-S_T}^+1_{S_t\leq H_t,t\in \brackk{0,T}}.
\end{align}
We will assume we are in the Black-Scholes framework and that $H\paren{t}$ is a step function.
If $\xi_i = 1_{U_i \leq p_i}$, where $U_i\sim \textrm{Unif(0,1)}$ the
\begin{align}
\label{a:eq:1}
e^{-rT}\paren{K-S_T}^{+}\prod_{i=0}^{m-1}\xi_i\\
\label{a:eq:2}
e^{-rT}\paren{K-S_T}^{+}\prod_{i=0}^{m-1}{p_i}.
\end{align}
are unbiased estimators of the option price.

\subsection{Calculate $p_i$}
We calculate an explicit expression for $p_i$
\begin{align}
p_i &= P\paren{\max_{t_i\leq t \leq t_{i+1}}S_t\left\vert\right. S_{t_i},S_{t_{i+1}}}\nonumber\\
&= P\left(S_{t_i}e^{\paren{r-\frac{\sigma^2}{2}}\paren{t-t_i}+\sigma\paren{W_t-W_{t_i}}}\leq H_i\vert S_{t_i},S_{t_{i+1}}\right)\nonumber\\
&=P\left(\max_{t_i\leq t \leq t_{i+1}} e^{\sigma W_t}\leq \frac{H_i}{S_{t_i}}e^{-\paren{r-\frac{\sigma^2}{2}}\paren{t_{i+1}-t_i}+\sigma W_{t_i}}\vert W_{t_i},W_{t_{i+1}}\right)\nonumber\\
&=P\left(\max_{t_i\leq t \leq t_{i+1}} \paren{W_t - W_{t_i}}\leq \sigma^{-1}\paren{\log\frac{H_i}{S_{t_i}} - \log S_{t_{i+1}}}+W_{t_{i+1}}-W_{t_i}\vert W_{t_i},W_{t_{i+1}}\right)\nonumber\\
&=1-\exp{\paren{-2\sigma^{-1}\paren{\log\frac{H_i}{S_{t_i}} - \log S_{t_{i+1}}}\paren{W_{t_{i+1}}-W_{t_i}+\sigma^{-1}\paren{\log\frac{H_i}{S_{t_i}} - \log S_{t_{i+1}}}}/\paren{t_{i+1} - t_i}}}
\end{align}
where we used the hint given in the exercise in the last equality.
\subsection{Estimator efficiency}
We prove the claim that the expected value of the estimators is the same. We have the following
\begin{align}
E&\brackk{\paren{K-S_T}^{+}\prod_{i=0}^{m-1}{\xi_i}} =  E\brackk{\paren{K-S_T}^{+}E\brackk{\prod_{i=0}^{m-1}{\xi_i}\left\vert\right. S_T}}\nonumber\\
&=E\brackk{\paren{K-S_T}^{+}E\brackk{E\brackk{\xi_{m-1}\prod_{i=0}^{m-2}{\xi_i}\vertt S_{t_{m-1}},S_{t_{m}}}\vertt S_T}}\nonumber\\
&=E\brackk{\paren{K-S_T}^{+}E\brackk{\xi_{m-1}E\brackk{\xi_{m-1}\prod_{i=0}^{m-2}{\xi_i}\vertt
 S_{t_{m-1}},S_{t_{m}}}\vertt S_T}}\nonumber\\
&=E\brackk{\paren{K-S_T}^{+}E\brackk{\xi_{m-1}E\brackk{E\brackk{\xi_{m-2}\prod_{i=0}^{m-3}{\xi_i}\vertt S_{t_{m-2}},S_{t_{m-1}}}\vertt S_{t_{m-1}},S_{t_{m}}}\vertt S_T}}\nonumber\\
&=E\brackk{\paren{K-S_T}^{+}E\brackk{\xi_{m-1}E\brackk{\xi_{m-2}E\brackk{\prod_{i=0}^{m-3}{\xi_i}\vertt S_{t_{m-2}},S_{t_{m-1}}}\vertt S_{t_{m-1}},S_{t_{m}}}\vertt S_T}}\nonumber\\
&=E\brackk{\paren{K-S_T}^{+}E\brackk{\xi_{m-1}E\brackk{\xi_{m-2}E\brackk{\cdots E\brackk{\xi_1 E\brackk{\xi_0\vertt S_{t_0},S_{t_1}}\vertt S_{t_1}, S_{t_2}}\cdots\vertt S_{t_{m-2}},S_{t_{m-1}}}\vertt S_{t_{m-1}},S_{t_{m}}}\vertt S_T}}\nonumber\\
&=E\brackk{\paren{K-S_T}^{+}E\brackk{\xi_{m-1}E\brackk{\xi_{m-2}E\brackk{\cdots E\brackk{\xi_1 p_0\vertt S_{t_1}, S_{t_2}}\cdots\vertt S_{t_{m-2}},S_{t_{m-1}}}\vertt S_{t_{m-1}},S_{t_{m}}}\vertt S_T}}\nonumber\\
&=E\brackk{\paren{K-S_T}^{+}E\brackk{\xi_{m-1}E\brackk{\xi_{m-2}E\brackk{\cdots p_1 p_0\cdots\vertt S_{t_{m-2}},S_{t_{m-1}}}\vertt S_{t_{m-1}},S_{t_{m}}}\vertt S_T}}\nonumber\\
&=E\brackk{\paren{K-S_T}^{+}E\brackk{\xi_{m-1}E\brackk{\xi_{m-2}\prod_{i=0}^{m-3}p_i\vertt S_{t_{m-2}},S_{t_{m-1}}}\vertt S_{t_{m-1}},S_{t_{m}}}\vertt S_T}\nonumber\\
&=E\brackk{\paren{K-S_T}^{+}E\brackk{\xi_{m-1}\prod_{i=0}^{m-2}p_i\vertt S_T}}\nonumber\\
&=E\brackk{\paren{K-S_T}^{+}\prod_{i=0}^{m-2}p_i E\brackk{\xi_{m-1}\vertt S_T}}\nonumber\\
&=E\brackk{\paren{K-S_T}^{+}\prod_{i=0}^{m-1}p_i}.
\end{align}
Indeed, this follows from the tower property and the fact that
\begin{align}
E\paren{\xi_i\vertt S_{t_i},S_{t_{i+1}}} = E\paren{1_{U_i\leq p_i}\vertt S_{t_i},S_{t_{i+1}}} = P\paren{U_i\leq p_i\vertt S_{t_i},S_{t_{i+1}}} = p_i.
\end{align}
It follows that 
\begin{align}
E\brackk{e^{-rT}\paren{K-S_T}^{+}\prod_{i=0}^{m-1}{\xi_i}} = E\brackk{e^{-rT}\paren{K-S_T}^{+}\prod_{i=0}^{m-1}{p_i}}.
\end{align}
Let $\mu = E\brackk{e^{-rT}\paren{K-S_T}^{+}\prod_{i=0}^{m-1}{\xi_i}} = E\brackk{e^{-rT}\paren{K-S_T}^{+}\prod_{i=0}^{m-1}{p_i}}$ and consider the variance of the two estimators:
\begin{align}
\var & \paren{e^{-rT}\paren{K-S_T}^{+}\prod_{i=0}^{m-1}\xi_i} = E\brackk{e^{-2rT}\paren{\paren{K-S_T}^{+}}^2\prod_{i=0}^{m-1}\xi_i^2}-\mu^2\nonumber\\
= &E\brackk{e^{-2rT}\paren{\paren{K-S_T}^{+}}^2\prod_{i=0}^{m-1}{\xi_i}}-\mu^2\nonumber\\
= &E\brackk{e^{-2rT}\paren{\paren{K-S_T}^{+}}^2\prod_{i=0}^{m-1}p_i}-\mu^2\nonumber\\
\geq &E\brackk{e^{-2rT}\paren{\paren{K-S_T}^{+}}^2\prod_{i=0}^{m-1}p_i^2}-\mu^2\nonumber\\
=& \var\paren{e^{-rT}\paren{K-S_T}^{+}\prod_{i=0}^{m-1}{p_i}}
\end{align}
We thus conclude that the estimator in \eqref{a:eq:2} is the most efficient of the estimators given.


\subsection{Pseudocode}
The following algorithm\vref{Problem1Algo} generates an estimate for the "up-and-put" option using the most efficient of the discussed estimators.
\begin{algorithm}
\caption{Generate an estimate of $E\brackk{e^{-rT}\paren{K-S_T}^{+}\prod_{i=0}^{m-1}{p_i}}$}
\label{Problem1Algo}
\begin{algorithmic}[1]
	\REQUIRE Interest rate $r$, volatility $\sigma$, Initial stock price $S_0$, strike $K$, step function $H\paren{t}$, number of evaluations $N$, time of expiration $T$, number of subdivisions $m$ of $\brackk{0;T}$.
	\ENSURE An estimate of $\hat\mu = E\brackk{e^{-rT}\paren{K-S_T}^{+}\prod_{i=0}^{m-1}{p_i}}$.
%  \STATE $r \leftarrow 0.04$
%  \STATE $\sigma \leftarrow 0.3$
%  \STATE $S_0 \leftarrow 100$
%  \STATE $T \leftarrow 5$
%  \STATE $K \leftarrow 120$
%  \STATE $H(t) \leftarrow 105 + 3\lfloor t\rfloor$
%  \STATE $m \leftarrow 5$
%  \STATE $N \leftarrow 10000$
  \STATE $\hat\mu \leftarrow 0$
  \FOR{$n \leftarrow 1$ to $N$}
  	\STATE $P \leftarrow 1$
	  \FOR{$i \leftarrow 0$ to $m-1$}
	  	\STATE $Z_{i+1} \sim N(0,1)$
			\STATE $W_{i+1} \leftarrow W_i + Z_{i+1}$
			\STATE $S_{t_{i+1}} \leftarrow S_{t_i}\exp \paren{\paren{r-\frac{\sigma^2}{2}}\paren{t_{i+1}-t_i} + 									\sigma\sqrt{t_{i+1}-t_i}Z_{i+1}}$
			\STATE $H_i \leftarrow H\paren{t_i}$
			\STATE $C \leftarrow  \log\frac{H_i}{S_{t_i}} - \log S_{t_{i+1}}$
	    \STATE $p \leftarrow 1-\exp\paren{-2\sigma^{-1} C \paren{Z_{i+1}+\sigma^{-1}C}\paren{t_{i+1} - t_i}}$
%			\STATE $p_i \leftarrow 1-\exp{\paren{-2\sigma^{-1}\paren{\log\frac{H_i}{S_{t_i}} - \log 															S_{t_{i+1}}}\paren{W_{t_{i+1}}-W_{t_i}+\sigma^{-1}\paren{\log\frac{H_i}{S_{t_i}} - \log 											S_{t_{i+1}}}}/\paren{t_{i+1} - t_i}}}$
			\STATE $P \leftarrow P\cdot p$
		\ENDFOR
	\IF{$S_{t_m} < K$}
		\STATE $\hat\mu \leftarrow \hat\mu + \paren{K - S_{t_m}}\cdot P$
	\ENDIF
  \ENDFOR
  \STATE $\hat\mu \leftarrow \hat\mu\exp\paren{-rT}/N$
  \RETURN $\hat\mu$
\end{algorithmic}
\end{algorithm}
An implementation of this algorithm can be found in appendix \ref{code1}.

Using algorithm~\vref{Problem1Algo}, with $N=10000$, produces the following results
\begin{verbatim}
> mu(sample)
[1] 25.03
> error(sample)
[1] 0.6234
\end{verbatim}
Thus the confidence bounds are $\brackk{24.41, 25.66}$.
\newpage
